Search Results

Documents authored by Souvaine, Diane L.

Document
DOI: 10.4230/LIPIcs.ESA.2023.6
Reconfiguration of Polygonal Subdivisions via Recombination

Authors: Hugo A. Akitaya, Andrei Gonczi, Diane L. Souvaine, Csaba D. Tóth, and Thomas Weighill

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Motivated by the problem of redistricting, we study area-preserving reconfigurations of connected subdivisions of a simple polygon. A connected subdivision of a polygon ℛ, called a district map, is a set of interior disjoint connected polygons called districts whose union equals ℛ. We consider the recombination as the reconfiguration move which takes a subdivision and produces another by merging two adjacent districts, and by splitting them into two connected polygons of the same area as the original districts. The complexity of a map is the number of vertices in the boundaries of its districts. Given two maps with k districts, with complexity O(n), and a perfect matching between districts of the same area in the two maps, we show constructively that (log n)^O(log k) recombination moves are sufficient to reconfigure one into the other. We also show that Ω(log n) recombination moves are sometimes necessary even when k = 3, thus providing a tight bound when k = 3.
Cite as

Hugo A. Akitaya, Andrei Gonczi, Diane L. Souvaine, Csaba D. Tóth, and Thomas Weighill. Reconfiguration of Polygonal Subdivisions via Recombination. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.ESA.2023.6,
  author =	{A. Akitaya, Hugo and Gonczi, Andrei and Souvaine, Diane L. and T\'{o}th, Csaba D. and Weighill, Thomas},
  title =	{{Reconfiguration of Polygonal Subdivisions via Recombination}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.6},
  URN =		{urn:nbn:de:0030-drops-186598},
  doi =		{10.4230/LIPIcs.ESA.2023.6},
  annote =	{Keywords: configuration space, gerrymandering, polygonal subdivision, recombination}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.9
Circumscribing Polygons and Polygonizations for Disjoint Line Segments

Authors: Hugo A. Akitaya, Matias Korman, Mikhail Rudoy, Diane L. Souvaine, and Csaba D. Tóth

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
Given a planar straight-line graph G=(V,E) in R^2, a circumscribing polygon of G is a simple polygon P whose vertex set is V, and every edge in E is either an edge or an internal diagonal of P. A circumscribing polygon is a polygonization for G if every edge in E is an edge of P. We prove that every arrangement of n disjoint line segments in the plane has a subset of size Omega(sqrt{n}) that admits a circumscribing polygon, which is the first improvement on this bound in 20 years. We explore relations between circumscribing polygons and other problems in combinatorial geometry, and generalizations to R^3. We show that it is NP-complete to decide whether a given graph G admits a circumscribing polygon, even if G is 2-regular. Settling a 30-year old conjecture by Rappaport, we also show that it is NP-complete to determine whether a geometric matching admits a polygonization.
Cite as

Hugo A. Akitaya, Matias Korman, Mikhail Rudoy, Diane L. Souvaine, and Csaba D. Tóth. Circumscribing Polygons and Polygonizations for Disjoint Line Segments. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{akitaya_et_al:LIPIcs.SoCG.2019.9,
  author =	{Akitaya, Hugo A. and Korman, Matias and Rudoy, Mikhail and Souvaine, Diane L. and T\'{o}th, Csaba D.},
  title =	{{Circumscribing Polygons and Polygonizations for Disjoint Line Segments}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.9},
  URN =		{urn:nbn:de:0030-drops-104136},
  doi =		{10.4230/LIPIcs.SoCG.2019.9},
  annote =	{Keywords: circumscribing polygon, Hamiltonicity, extremal combinatorics}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.269
Algorithms for Designing Pop-Up Cards

Authors: Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, André Schulz, Diane L. Souvaine, Giovanni Viglietta, and Andrew Winslow

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We prove that every simple polygon can be made as a (2D) pop-up card/book that opens to any desired angle between 0 and 360°. More precisely, given a simple polygon attached to the two walls of the open pop-up, our polynomial-time algorithm subdivides the polygon into a single-degree-of-freedom linkage structure, such that closing the pop-up flattens the linkage without collision. This result solves an open problem of Hara and Sugihara from 2009. We also show how to obtain a more efficient construction for the special case of orthogonal polygons, and how to make 3D orthogonal polyhedra, from pop-ups that open to 90°, 180°, 270°, or 360°.
Cite as

Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, André Schulz, Diane L. Souvaine, Giovanni Viglietta, and Andrew Winslow. Algorithms for Designing Pop-Up Cards. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 269-280, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{abel_et_al:LIPIcs.STACS.2013.269,
  author =	{Abel, Zachary and Demaine, Erik D. and Demaine, Martin L. and Eisenstat, Sarah and Lubiw, Anna and Schulz, Andr\'{e} and Souvaine, Diane L. and Viglietta, Giovanni and Winslow, Andrew},
  title =	{{Algorithms for Designing Pop-Up Cards}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{269--280},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.269},
  URN =		{urn:nbn:de:0030-drops-39407},
  doi =		{10.4230/LIPIcs.STACS.2013.269},
  annote =	{Keywords: geometric folding, linkages, universality}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact